A three-dimensional graphics display system is employed in, for example, a mechanical engineering computer-aided design system to provide on a display screen two-dimensional images having three-dimensional qualities. These display images are rendered from image data that are arranged in a preselected format and describe or model a solid, physical, three-dimensional object.
One such image data format is constructive solid geometry (CSG), in which a solid object is modeled as a combination of primitive solids that may include but are not limited to blocks, spheres, and cylinders. Boolean set operators such as union and intersection are used to combine various ones of the primitive solids and, thereby, assemble a model of the solid object. For example, a solid object that includes a spherical knob at the end of a cylindrical shaft could be modeled as the union of a sphere and a cylinder.
The primitive solids employed in the CSG format provide a user with primary shapes from which he can assemble a model of a particular physical object. The primitive solids are, however, provided primarily as a convenience for the user. Within the graphics display system, each primitive solid is represented as a combination of one or more "halfspaces," which are themselves combined by Boolean set operators in a manner similar to that in which the primitive solids are combined. Although such a halfspace-based CSG format is sometimes called a normalized CSG format, it will hereinafter be distinguished from the primary solid-based CSG format only when necessary for clarity.
The CSG image data describing a solid object are represented in mathematical form. The physical, three-dimensional shape of the object is modeled in the CSG format with mathematical expressions defined in a mathematical, three-dimensional object space. Although it is a mathematical construct, the three-dimensional object space is often referred to as though it were a physical, three-dimensional space.
In a normalized CSG format, the boundary of each halfspace separates the object space into an interior region that lies inside the halfspace and an exterior region that lies outside the halfspace. The boundary of each halfspace is defined by an implicit function f(x,y,z)=0. The halfspace itself is defined by a mathematical expression of the form f(x,y,z).ltoreq.0, in which points that satisfy the inequality correspond to the interior of the halfspace. Examples of typical boundaries used to define halfspaces include spheres, cylinders of infinite length, and infinite planes.
The normalized CSG image data representing a primitive solid can comprise any number of halfspaces. For example, a primitive solid sphere is represented as a single spherical halfspace, and a primitive solid rectangular block is represented as the intersection of six orthogonally aligned planar halfspaces in which the boundaries of the six planar halfspaces define the six faces of the block.
Although the CSG image data representing a solid object provide a compact and complete description of the object, the rendering of a shaded image from the CSG image data is typically very slow. Some methods of rendering an image derive the surface of the object from the CSG image data. Such methods include a polygon approximation method, a solids intersection method, a ray casting method, and a spatial subdivision method.
The polygon approximation method approximates the surface of each primitive solid with a polyhedron that is formed from a plurality of adjacent polygons. For example, a cylinder of finite length could be approximated as a tubular, n-sided polyhedron in which the n sides are long, narrow polygons, (i.e. rectangles) that approximate the tubular shape of the cylinder.
In a model comprising more than one primitive solid, the polyhedral approximations for the different primitive solids are combined in accordance with a relatively simple polygon intersection algorithm. A problem with this method is that it generates a very large number of polygons for CSG image data representing even a relatively simple object, thereby requiring a great deal of memory space and a large number of computations to derive the surface of the object. As a consequence, the polygon approximation method is a relatively slow method of rendering images
The solids intersection method employs a different intersection algorithm for each pair of primitive solids. This method suffers from the disadvantage of being inflexible in that it is cumbersome for a display system that employs more than three types of primitive solids. For example, a graphics display system that employs only planes and cylinders as its primitive solids requires three intersection algorithms to cover the different ways planes can intersect cylinders. In contradistinction, a system that employs planes, cylinders, cones, and tori as its primitive solids requires ten intersection algorithms and a variety of special rules to cover certain particular intersection possibilities.
Ray casting is a relatively simple, though computationally intensive, method of rendering an image from CSG image data. Ray casting determines, for each pixel in an image, which halfspace in the CSG image data is visible on the display screen. The CSG image data form a model of the object and are defined in an object space, which is considered to be aligned with and positioned behind the display screen. A "ray" is mathematically "directed" through each pixel on the display screen and toward the model. The "ray" passes at a perpendicular angle through the display screen and into the object space. The intersection and union information of all the CSG image data representing the object are reviewed to identify which one of the halfspaces in the CSG data is first intersected by the "ray" and is, therefore, to be rendered on the display screen. Each pixel for which there is an identified halfspace is rendered a color corresponding to the halfspace, thereby forming an image of the object in a pixel-by-pixel fashion. Ray casting can render a high quality image but is very slow because all of the CSG image data are reviewed for each pixel in the image.
Spatial subdivision, as described by Woodwark et al., "The Derivation of Graphics from Volume Models by Recursive Subdivision of the Object Space," Procedinos CG-80 Conference (1980), is a relatively fast method of rendering on a display screen an image of an object that is described by planar, linear halfspaces. The object space within which three-dimensional objects are described is considered to be aligned with and positioned behind the display screen. The object space is recursively subdivided into volume elements for each of which the halfspaces in the CSG image data are classified as being FULL, EMPTY, or PARTIAL.
FIG. 1 shows in two dimensions an exemplary object space 2 in which a prior art planar halfspace 3 lies. At each level in the subdivision of object space 2, halfspace 3 is classified as FULL whenever a volume element 4 lies entirely inside the halfspace, as EMPTY whenever a volume element 5 lies entirely outside the halfspace, and as PARTIAL whenever a volume element 6 lies partly inside and partly outside the halfspace.
In volume elements having halfspaces classified as FULL or EMPTY, the CSG image data are simplified or reduced in accordance with simplification identities described by Woodwark et al. The simplification identities reduce the CSG image data by characterizing halfspaces as active or inactive depending on whether their classifications are material to the rendering of the image.
Volume elements in which the CSG image data have been reduced to a single active halfspace that is classified as FULL are assigned a color corresponding to the halfspace and, therefore, the model of the object. Volume elements in which the CSG image data have been reduced to include no active halfspaces correspond to an empty region in the object space through which other volume elements can be observed. Volume elements in which the CSG image include two or more active halfspaces that are classified as FULL are subdivided and reclassified.
Volume elements in which the image data are reduced to no active halfspaces or a single active halfspace that is classified as FULL correspond to portions of the display screen that can be rendered as an empty region or as part of the model, respectively. Such volume elements do not, therefore, require subdivision. Other volume elements undergo further subdivision until either the image data in each resulting volume element are reduced to no active halfspaces or a single active halfspace that is classified as FULL, or until the length of a side of the resulting volume element is equal to the length of an image pixel on the display screen. Such a volume element is called a voxel. Since the image data are typically reduced to no active halfspaces or a single active halfspace that is classified as FULL for volume elements that are substantially larger than a voxel, spatial subdivision is a much faster method of rendering images than is ray casting.
The volume elements are of either a cubical or a rectangular parallelepiped shape. The spatial subdivision method of Woodwark et al., which is directed only to planar halfspaces, employs a relatively simple planar classification method for classifying such halfspaces. In particular, the boundaries of planar halfspaces are defined by monotonic, linear functions. In the classification of such halfspaces it is, therefore, sufficient to determine whether each corner or vertex of a volume element is inside the halfspace.
For example, a planar halfspace can be defined by the inequality f(x,y,z).ltoreq.0 in which f(x,y,z) is a linear, implicit function. Whenever the value of the function f(x,y,z) is less than or equal to zero at each of the corners of a volume element, the halfspace is classified as FULL for that volume element. Whenever the value of the function f(x,y,z}is greater than zero at each of the corners of the volume element, the halfspace is classified as EMPTY for that volume element. Whenever the value of the function f(x,y,z) is greater than zero at one or more of the corners and less than or equal to zero at another corner, the halfspace is classified as PARTIAL for that volume element.
Typically, some volume elements in which the image data are reduced to a single active halfspace that is classified as FULL are not rendered on the display screen. Such volume elements are positioned behind other volume elements having single active halfspaces that are classified as FULL and are, therefore, occluded. As a result, it is necessary in the rendering of the image to determine not only whether a volume element has a single active halfspace that is classified as FULL, but also whether such a volume element is occluded by another volume element having a single active halfspace that is classified as FULL. The three-dimensional appearance of the image is enhanced by not rendering occluded volume elements.
The detection of occluding volume elements not only enhances the three-dimensional appearance of an image, but also increases the speed at which the image is rendered. Subdividing the object space sequentially from the front of the object space (i.e., near the display screen) to the rear of the object space renders unnecessary the classification of the halfspaces in any occluded volume elements, and thereby reduces the number of classifications and increases the speed at which the image is rendered.
The classification method of Woodwark et al. cannot accurately classify nonplanar halfspaces. In particular, a typical nonplanar halfspace cannot be classified in accordance with whether each corner of a volume element is inside the halfspace. The reason is that a nonplanar halfspace could contain each corner of a volume element while not containing the entire volume element. Since such a halfspace would be incorrectly classified, the resulting image would be incorrectly rendered. As a result, the spatial subdivision method as developed by Woodwark et al., which method employs the planar classification method, cannot be used to render images represented by nonplanar halfspaces.